class Solution {
public:
	string intToRoman(int num) {
		string res;
		if (num > 3999) return res;
		vector<pair<int, char>> vt{ {1000,'M'},{500,'D'},{100,'C'},{50,'L'},{10,'X'},{5,'V'},{1,'I'} };
		for (int i = 0;i < vt.size();i++)
		{
			int temp = 0;
			if (i + 1 < vt.size())
			{
				temp = num / vt[i + 1].first;

			}

			if (temp == 9 && i%2==1)
			{
				i++;
			}
			else
			{
				temp = num / vt[i].first;
			}
			num = num % vt[i].first;

			if (temp == 4)
			{
				res.push_back(vt[i].second);
				res.push_back(vt[i - 1].second);
			}
			else if (temp == 9)
			{
				res.push_back(vt[i].second);
				res.push_back(vt[i - 2].second);
			}
			else
			{
				for (int j = 0;j < temp;j++)
				{
					res.push_back(vt[i].second);
				}
			}

		}
		return res;
	}
};